package Solution.problem074;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/06/11 18:21
 */
public class Solution02 {
    public static boolean searchMatrix(int[][] matrix, int target) {
        /** 边界判断*/
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return false;
        }
        /*二分查找找到对应的行*/
        return checkContain(matrix, rows, cols, target);
    }

    private static boolean checkContain(int[][] matrix,  int rows, int cols, int target) {
        int startRow = 0;
        int endRow = rows - 1;
        while (startRow <= endRow) {
            int mid = (startRow + endRow) / 2;
            int rowStartCol = matrix[mid][0];
            int rowEndCol = matrix[mid][cols - 1];
            if (target < rowStartCol) {
                endRow = mid - 1;
            } else if (target > rowEndCol) {
                startRow = mid + 1;
            } else {
                /*找到指定的行，继续查找*/
                int startCol = 0;
                int endCol = cols - 1;
                while (startCol <= endCol) {
                    int colMid = (startCol + endCol) / 2;
                    if (target < matrix[mid][colMid]) {
                        endCol = colMid - 1;
                    } else if (target > matrix[mid][colMid]) {
                        startCol = colMid + 1;
                    } else {
                        return true;
                    }
                }
                return false;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
        System.out.println(searchMatrix(matrix, 11));
        System.out.println(searchMatrix(matrix, 4));
        System.out.println(searchMatrix(matrix, 0));
        System.out.println(searchMatrix(matrix, 51));
        System.out.println(searchMatrix(matrix, 3));
    }
}
